package com.yun.algorithm.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 贪心算法
 * 活动时间安排问题
 */
public class ActivitySelectionProblem {

    public static void main(String[] args) {
        Activity[] activities=new Activity[]{
                new Activity(1,2,4),
                new Activity(0,1,3),
                new Activity(2,3,5)
        };
        Arrays.sort(activities, Comparator.comparingInt(Activity::getFinish));
        System.out.println(Arrays.toString(activities));

        select(activities,activities.length);
    }
    static class Activity {
        int index;
        int start;
        int finish;

        public Activity(int index, int start, int finish) {
            this.index = index;
            this.start = start;
            this.finish = finish;
        }

        public int getFinish(){
            return finish;
        }

        @Override
        public String toString() {
            return "Activity(" + index + ')';
        }
    }

    private static void select(Activity[] activities, int n) {
        List<Activity> result=new ArrayList<>();
        Activity prev=activities[0];
        result.add(prev);
        for (int i = 1; i < n; i++) {
            Activity curr = activities[i];
            if(curr.start>= prev.finish){
                result.add(curr);
                prev=curr;
            }
        }
        for (Activity activity : result) {
            System.out.println(activity);
        }
    }
}
